package leetcode.f1t100;

/**
 * 数独填充
 * 每行每列+每个九宫格内的数字
 * https://leetcode.com/problems/sudoku-solver/
 */
public class Q37_SudokuSolver {


    public static void solveSudoku(char[][] board) {
        /**
         * flag[0][m][n]表示第m行有n值;
         * flag[1][m][n]表示第m列有n值;
         * flag[2][m][n]表示第m个九宫格有n值;
         */
        boolean[][][] flag = new boolean[3][9][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if ('.' != board[i][j]) {
                    setFlag(flag, i, j, board[i][j], true);
                }
            }
        }
        func(board, 0, 0, flag);
    }

    public static void setFlag(boolean[][][] flag, int i, int j, char value, boolean b) {
        int intVal = value - '0';
        flag[0][i][intVal] = b;
        flag[1][j][intVal] = b;
        flag[2][3 * (i / 3) + (j / 3)][intVal] = b;
    }

    public static boolean checkFlag(boolean[][][] flag, int i, int j, int value) {
        return !(flag[0][i][value] || flag[1][j][value] || flag[2][3 * (i / 3) + (j / 3)][value]);
    }

    public static boolean func(char[][] board, int i, int j, boolean[][][] flag) {
        if ('.' != (board[i][j])) {
            return funcNext(board, i, j, flag);
        }

        for (int testV = 1; testV <= 9; testV++) {
            if (checkFlag(flag, i, j, testV)) {
                board[i][j] = (char) (testV + '0');
                setFlag(flag, i, j, board[i][j], true);
                if (funcNext(board, i, j, flag)) {
                    return true;
                }
                setFlag(flag, i, j, board[i][j], false);
                board[i][j] = '.';
            }
        }
        return false;
    }

    public static boolean funcNext(char[][] board, int i, int j, boolean[][][] flag) {
        j++;

        if (i == 8 && j == 9) {
            return true;
        }
        if (j == 9) {
            return func(board, i + 1, 0, flag);
        }
        return func(board, i, j, flag);

    }


    public static void main(String[] args) {


        char[][] board = new char[][]
                {
                        {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                        {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                        {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                        {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                        {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                        {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                        {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                        {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                        {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
                };
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }

        System.out.println();
        System.out.println();

        solveSudoku(board);

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }
}
